package com.cyy.test_t_5_;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @Description 剑指Offer t_59 - 按之字形顺序打印二叉树
 * 题目描述：
 * 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，
 * 第三行按照从左到右的顺序打印，其他行以此类推。
 * @Author Crystal
 * @Date 2019/7/15 7:07
 * @Version 1.0
 **/
public class t_59 {
    /**
     * 定义二叉树
     */
    private static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;
        private TreeNode parent;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }
    }

    public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        /**
         * 两个栈s1,s2，奇数层，左节点先入栈s1，右节点后入栈s1,
         * 偶数层，右节点先入栈s1，左节点后入栈s1
         *
         */

        //用于选择存s1还是s2
        boolean next = true;
        //s1存奇数层节点
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        s1.push(pRoot);
        //s2存偶数层节点
        Stack<TreeNode> s2 = new Stack<TreeNode>();

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();

        if(pRoot == null) return list;

        while(!s1.empty() || !s2.empty()){
            if(next){
                ArrayList<Integer> temp1 = new ArrayList<>();
                while(!s1.empty()){
                    TreeNode node = s1.pop();
                    if(node != null){
                        temp1.add(node.val);
                        System.out.print(node.val + " ");
                        s2.push(node.left);
                        s2.push(node.right);
                    }
                }
                if(!temp1.isEmpty()){
                    list.add(temp1);
                    next = !next;
                    System.out.println();
                }
            } else {
                ArrayList<Integer> temp2 = new ArrayList<>();
                while(!s2.empty()){
                    TreeNode node = s2.pop();
                    if(node != null){
                        temp2.add(node.val);
                        System.out.print(node.val + " ");
                        s1.push(node.right);
                        s1.push(node.left);
                    }
                }
                if(!temp2.isEmpty()){
                    list.add(temp2);
                    next = !next;
                    System.out.println();
                }
            }
        }
        return list;
    }

    private static void assemble(TreeNode node,
                                 TreeNode left,
                                 TreeNode right,
                                 TreeNode parent) {
        node.left = left;
        node.right = right;
        node.parent = parent;
    }

    public static void main(String[] args) {
        test01();
    }

    //                            1
    //                  2                   3
    //             4         5          6          7
    //          8     9   10   11   12   13    14   15
    public static void test01() {
        TreeNode n1 = new TreeNode(1); // 12
        TreeNode n2 = new TreeNode(2); // 10
        TreeNode n3 = new TreeNode(3); // 14
        TreeNode n4 = new TreeNode(4); // 9
        TreeNode n5 = new TreeNode(5); // 11
        TreeNode n6 = new TreeNode(6); // 13
        TreeNode n7 = new TreeNode(7); // 15
        TreeNode n8 = new TreeNode(8); // 4
        TreeNode n9 = new TreeNode(9); // 2
        TreeNode n10 = new TreeNode(10); // 5
        TreeNode n11 = new TreeNode(11); // 1
        TreeNode n12 = new TreeNode(12); // 6
        TreeNode n13 = new TreeNode(13); // 3
        TreeNode n14 = new TreeNode(14); // 7
        TreeNode n15 = new TreeNode(15); // null

        assemble(n1, n2, n3, null);
        assemble(n2, n4, n5, n1);
        assemble(n3, n6, n7, n1);
        assemble(n4, n8, n9, n2);
        assemble(n5, n10, n11, n2);
        assemble(n6, n12, n13, n3);
        assemble(n7, n14, n15, n3);
        assemble(n8, null, null, n4);
        assemble(n9, null, null, n4);
        assemble(n10, null, null, n5);
        assemble(n11, null, null, n5);
        assemble(n12, null, null, n6);
        assemble(n13, null, null, n6);
        assemble(n14, null, null, n7);
        assemble(n15, null, null, n7);

        System.out.println(Print(n1));
    }
}